Version Vectors

Version vectors let a distributed system determine whether one version includes another or whether two versions were updated concurrently. Each participant keeps a counter and updates it when communicating. Equal vectors mean the versions contain the same updates. Two versions are concurrent when neither vector is greater than or equal to the other in every position; one vector causally follows another when it is at least as large in every position and larger in at least one. The same way as Lamport Timestamps, we use the max values of the peers whenever synchronizing.

Implementation

Keep an Vector of integers for each process. Increment them at each operation. Compare the values to check if they are either concurrent (equal) or have any causality (by checking dominance - less than or greater than) #versionvectors #vectors #version #distributedsystems

Comparing with Lamport Timestamps

The key difference is that version vectors keep one counter per participant and can identify concurrent updates, whereas Lamport timestamps provide an order but cannot prove that two events were concurrent. Lamport cannot track concurrency since they are global values and is much more simpler than Version Vectors to implement. Complexity-wise Version Vectors are in disavantage as they need to track N processes (integers) and Lamport Timestamps are unique/global per node.